#ifndef __SKIP_LIST_H__
#define __SKIP_LIST_H__

#include <vector>
#include <iostream>

#include "bilinkedlist/bilinkedlist.h"


namespace algo
{

template<typename K, typename V>
class SkipList
{

private:

struct SkipNode
{
    K key;
    V value;

    SkipNode(K k, V v) : key(k), value(v)   {   }
};

struct IndexNode;

typedef std::shared_ptr<typename algo::BiLinkedList<IndexNode>::BiNode> IndexBiNodePtr;
typedef std::shared_ptr<typename algo::BiLinkedList<SkipNode>::BiNode> SkipBiNodePtr;

// union Down
// {
//     IndexBiNodePtr index;
//     SkipBiNodePtr data;
// };

struct IndexNode
{
    K key;
    //Down down;
    IndexBiNodePtr index;
    SkipBiNodePtr data;
    
};

public:

    bool add(const K& key, const V &value);

    bool get(const K& key, V &value);

private:
    bool add_c(const SkipNode &newNode, const IndexBiNodePtr &pIndexBiNode, int level, bool forward, IndexNode &outIndexNode);

    bool add_data(const SkipNode &newNode, const IndexBiNodePtr &pIndexBiNode, bool forward,
        IndexNode &newIndexNode);

    bool addDataForward(const SkipNode &newNode, const IndexBiNodePtr &pIndexBiNode,
        IndexNode &newIndexNode);

    bool addDataReverse(const SkipNode &newNode, const IndexBiNodePtr &pIndexBiNode,
        IndexNode &newIndexNode);

    bool GetIndexBiNodeInfo(const SkipNode &newNode, int level, bool forward, const IndexBiNodePtr &pIndexBiNode, 
        bool &outForward, IndexBiNodePtr &pOutIndexBiNode, IndexNode &outIndexNode);

    bool GetForwardIndexBiNodeInfo(const SkipNode &newNode, int level, const IndexBiNodePtr &pIndexBiNode, 
        bool &outForward, IndexBiNodePtr &pOutIndexBiNode, IndexNode &outIndexNode);

    bool GetReverseIndexBiNodeInfo(const SkipNode &newNode, int level, const IndexBiNodePtr &pIndexBiNode, 
        bool &outForward, IndexBiNodePtr &pOutIndexBiNode, IndexNode &outIndexNode);

private :

    bool get_c(const IndexBiNodePtr &pIndexBiNode, bool forward, const K& key, V &value, int level);

    bool getData(const IndexBiNodePtr &pIndexBiNode, bool forward, const K& key, V &value);

    bool getDataFowrard(const IndexBiNodePtr &pIndexBiNode, const K& key, V &value);

    bool getDataReverse(const IndexBiNodePtr &pIndexBiNode, const K& key, V &value);

    bool getIndex(const IndexBiNodePtr &pIndexBiNode, bool forward, const K& key, V &value, IndexBiNodePtr &pOutIndexBiNode, bool &outFwd);

    bool getIndexForward(const IndexBiNodePtr &pIndexBiNode, const K& key, V &value, 
        IndexBiNodePtr &pOutIndexBiNode, bool &outFwd);

    bool getIndexReverse(const IndexBiNodePtr &pIndexBiNode, const K& key, V &value, 
        IndexBiNodePtr &pOutIndexBiNode, bool &outFwd);


public :
    void show_all();

private:

    static const int STEP = 3;

    std::vector<algo::BiLinkedList<IndexNode>> vecIndex;

    algo::BiLinkedList<SkipNode> list;
};

template<typename K, typename V>
bool SkipList<K, V>::add(const K& key, const V &value)
{
    bool ret = false;
    SkipNode node(key, value);

    if (list.empty())
    {
        list.append(node);
        return true;
    }

    int size = vecIndex.size();
    IndexNode newIndexNode;
    add_c(node, NULL, size + 1, true, newIndexNode);

    return ret;
}

template<typename K, typename V>
bool SkipList<K, V>::add_c(const SkipNode &newNode, const IndexBiNodePtr &pIndexBiNode, int level, bool forward, 
    IndexNode &outIndexNode)
{
    bool addIndex = false;
    if (0 == level)
    {
        addIndex = add_data(newNode, pIndexBiNode, forward, outIndexNode);
    }
    else
    {
        bool fwd = true;
        IndexBiNodePtr pCurIndexBiNode(NULL);
        addIndex = GetIndexBiNodeInfo(newNode, level, forward, pIndexBiNode, fwd, pCurIndexBiNode, outIndexNode);

        IndexNode indexNode;
        bool ret = add_c(newNode, pCurIndexBiNode, level - 1, fwd, indexNode);

        if (ret)
        {
            if (vecIndex.size() < level)
            {
                vecIndex.push_back(algo::BiLinkedList<IndexNode>());
                algo::BiLinkedList<IndexNode> &indexList = vecIndex.back();
                indexList.append(indexNode);
                addIndex = false;
            }
            else
            {
                algo::BiLinkedList<IndexNode> &indexList = vecIndex[level - 1];
                if (fwd)
                {
                    indexList.insertAfter(*pCurIndexBiNode, indexNode);
                }
                else
                {
                    indexList.insertBefore(*pCurIndexBiNode, indexNode);
                }
            }
        }
    }

    return addIndex;
}

template<typename K, typename V>
bool SkipList<K, V>::add_data(const SkipNode &newNode, const IndexBiNodePtr &pIndexBiNode, bool forward,
    IndexNode &newIndexNode)
{
    if (forward)
    {
        return addDataForward(newNode, pIndexBiNode, newIndexNode);
    }
    else
    {
        return addDataReverse(newNode, pIndexBiNode, newIndexNode);
    }
}

template<typename K, typename V>
bool SkipList<K, V>::addDataForward(
    const SkipNode &newNode, const IndexBiNodePtr &pIndexBiNode,
    IndexNode &newIndexNode)
{
    bool ret = false;
    int step = 0;
    newIndexNode.data = NULL;
    
    SkipBiNodePtr pIter;
    if (!pIndexBiNode)
    {
        pIter = list.getFirstNode();
    }
    else
    {
        pIter = (**pIndexBiNode).data;
    }

    for (; pIter != NULL; pIter = pIter->next, ++step)
    {
        SkipNode &iterNode = **pIter;
        if (iterNode.key == newNode.key)
        {
            iterNode.value = newNode.value;
            return false;
        }
        else if (newNode.key < iterNode.key)
        {
            if (step > STEP)
            {
                newIndexNode.key = newNode.key;
                newIndexNode.data = list.insertBefore(*pIter, newNode);
                return true;
            }
            else
            {
                list.insertBefore(*pIter, newNode);
                ret = false;
                ++step;
                break;
            }
        }
    }

    if (pIter == NULL)
    {
        if (step > STEP)
        {
            newIndexNode.key = newNode.key;
            newIndexNode.data = list.insertAfter(list.rbegin(), newNode);
            return true;
        }
        else
        {
            list.insertAfter(list.rbegin(), newNode);
            ret = false;
        }
    }
    else
    {
        IndexBiNodePtr pIndexBiNodeNext = pIndexBiNode->next;
        SkipBiNodePtr pSkipBiNodeNext = (pIndexBiNodeNext) ? (**pIndexBiNodeNext).data : NULL;
        for (; pIter != pSkipBiNodeNext; pIter = pIter->next, ++step)
        {
            if (step > STEP && !newIndexNode.data)
            {
                newIndexNode.key = (**pIter).key;
                newIndexNode.data = pIter;
            }
        }
        if (step >= 2*STEP)
        {
            ret = true;
        }
    }

    return ret;
}


template<typename K, typename V>
bool SkipList<K, V>::addDataReverse(
    const SkipNode &newNode, const IndexBiNodePtr &pIndexBiNode,
    IndexNode &newIndexNode)
{
    bool ret = false;
    int step = 0;
    newIndexNode.data = NULL;
    
    SkipBiNodePtr pIter;
    if (!pIndexBiNode)
    {
        pIter = list.getLastNode();
    }
    else
    {
        pIter = (**pIndexBiNode).data;
    }

    for (; pIter->prev != NULL; pIter = pIter->prev, ++step)
    {
        SkipNode &iterNode = **pIter;
        if (iterNode.key == newNode.key)
        {
            iterNode.value = newNode.value;
            return false;
        }
        else if (iterNode.key < newNode.key)
        {
            if (step > STEP)
            {
                newIndexNode.key = newNode.key;
                newIndexNode.data = list.insertAfter(*pIter, newNode);
                return true;
            }
            else
            {
                list.insertAfter(*pIter, newNode);
                ret = false;
                ++step;
                break;
            }
        }
    }

    if (pIter->prev == NULL)
    {
        if (step > STEP)
        {
            newIndexNode.key = newNode.key;
            newIndexNode.data = list.insertBefore(list.begin(), newNode);
            return true;
        }
        else
        {
            list.insertBefore(list.begin(), newNode);
            ret = false;
        }
    }
    else
    {
        IndexBiNodePtr pIndexBiNodePrev = pIndexBiNode->prev;
        SkipBiNodePtr pSkipBiNodePrev = (pIndexBiNodePrev) ? (**pIndexBiNodePrev).data : NULL;
        for (; pIter != pSkipBiNodePrev; pIter = pIter->prev, ++step)
        {
            if (step > STEP && !newIndexNode.data)
            {
                newIndexNode.key = (**pIter).key;
                newIndexNode.data = pIter;
            }
        }
        if (step >= 2*STEP)
        {
            ret = true;
        }
    }

    return ret;
}

template<typename K, typename V>
bool SkipList<K, V>::GetIndexBiNodeInfo(const SkipNode &newNode, int level, bool forward, 
    const IndexBiNodePtr &pIndexBiNode, bool &outForward, IndexBiNodePtr &pOutIndexBiNode,
    IndexNode &outIndexNode)
{
    if (vecIndex.size() < level)
    {
        K key;
        if (level == 1)
        {
            SkipBiNodePtr pIter = list.getFirstNode();
            key = (**pIter).key;
        }
        else
        {
            algo::BiLinkedList<IndexNode> &indexList = vecIndex[level - 2];
            IndexBiNodePtr pIter = indexList.getFirstNode();
            key = (**pIter).key;
        }
        if (key > newNode.key)
        {
            outForward = false;
        }
        else
        {
            outForward = true;
        }
            
        return false;
    }

    if (forward)
    {
        return GetForwardIndexBiNodeInfo(newNode, level, pIndexBiNode, 
                outForward, pOutIndexBiNode, outIndexNode);
    }
    else
    {
        return GetReverseIndexBiNodeInfo(newNode, level, pIndexBiNode, 
                outForward, pOutIndexBiNode, outIndexNode);
    }
}

template<typename K, typename V>
bool SkipList<K, V>::GetForwardIndexBiNodeInfo(const SkipNode &newNode, int level, const IndexBiNodePtr &pIndexBiNode, 
    bool &outForward, IndexBiNodePtr &pOutIndexBiNode, IndexNode &outIndexNode)
{
    bool ret = false;
    int step = 0;
    outIndexNode.index = NULL;
    algo::BiLinkedList<IndexNode> &indexList = vecIndex[level - 1];

    IndexBiNodePtr pIter;
    if (!pIndexBiNode)
    {
        pIter = indexList.getFirstNode();
    }
    else
    {
        pIter = (**pIndexBiNode).index;
    }

    IndexBiNodePtr pIterPrev;
    for (; pIter != NULL; pIter = pIter->next, ++step)
    {
        pIterPrev = pIter;
        if ((**pIter).key == newNode.key)
        {
            pOutIndexBiNode = pIter;
            return false;
        }
        else if (newNode.key < (**pIter).key)
        {
            pOutIndexBiNode = pIter;
            outForward = false;
            if (step > STEP)
            {
                outIndexNode.key = (**pIter).key;
                outIndexNode.index = pIter;
                return true;
            }
            else
            {
                return false;
            }
        }
        
    }
    if (pIter == NULL)
    {
        pOutIndexBiNode = pIterPrev;
        outForward = true;

        if (step > STEP)
        {
            outIndexNode.key = (**pOutIndexBiNode).key;
            outIndexNode.index = pOutIndexBiNode;
            ret = true;
        }
    }

    return ret;
}

template<typename K, typename V>
bool SkipList<K, V>::GetReverseIndexBiNodeInfo(const SkipNode &newNode, int level,  const IndexBiNodePtr &pIndexBiNode, 
    bool &outForward, IndexBiNodePtr &pOutIndexBiNode, IndexNode &outIndexNode)
{
    bool ret = false;
    int step = 0;
    outForward = true;
    outIndexNode.index = NULL;
    algo::BiLinkedList<IndexNode> &indexList = vecIndex[level - 1];

    IndexBiNodePtr pIter;
    if (!pIndexBiNode)
    {
        pIter = indexList.getLastNode();
    }
    else
    {
        pIter = (**pIndexBiNode).index;
    }

    IndexBiNodePtr pIterNext;
    for (; pIter->prev != NULL; pIter = pIter->prev, ++step)
    {
        pIterNext = pIter;
        if ((**pIter).key == newNode.key)
        {
            pOutIndexBiNode = pIter;
            return false;
        }
        else if ((**pIter).key < newNode.key)
        {
            pOutIndexBiNode = pIter;
            outForward = true;
            if (step > STEP)
            {
                outIndexNode.key = (**pIter).key;
                outIndexNode.index = pIter;
                return true;
            }
            else
            {
                return false;
            }
        }
        
    }
    if (pIter->prev == NULL)
    {
        pOutIndexBiNode = pIterNext;
        outForward = false;

        if (step > STEP)
        {
            outIndexNode.key = (**pOutIndexBiNode).key;
            outIndexNode.index = pOutIndexBiNode;
            ret = true;
        }
    }
    
    return ret;
}

template<typename K, typename V>
bool SkipList<K, V>::get(const K& key, V &value)
{
    return get_c(NULL, true, key, value, vecIndex.size());
}

template<typename K, typename V>
bool SkipList<K, V>::get_c(const IndexBiNodePtr &pIndexBiNode, bool forward, const K& key,  V &value, int level)
{
    if (level == 0)
    {
        return getData(pIndexBiNode, forward, key, value);
    }
    else
    {
        IndexBiNodePtr pNextIndexBiNode(NULL);
        bool outFwd = true;
        getIndex(pIndexBiNode, forward, key, value, pNextIndexBiNode, outFwd);
        return get_c(pNextIndexBiNode, outFwd, key, value, level - 1);
    }
}

template<typename K, typename V>
bool SkipList<K, V>::getData(const IndexBiNodePtr &pIndexBiNode, bool forward, const K& key, V &value)
{
   if (forward)
   {
       return getDataFowrard(pIndexBiNode, key, value);
   }
   else
   {
       return getDataReverse(pIndexBiNode, key, value);
   }
}

template<typename K, typename V>
bool SkipList<K, V>::getDataFowrard(const IndexBiNodePtr &pIndexBiNode, const K& key, V &value)
{
    SkipBiNodePtr pIter(NULL);
    if (!pIndexBiNode)
    {
        pIter = list.getFirstNode();
    }
    else
    {
        pIter = (**pIndexBiNode).data;
    }

    for (; pIter != NULL; pIter = pIter->next)
    {
        SkipNode &iterNode = **pIter;
        if (iterNode.key == key)
        {
            value = iterNode.value;
            return true;
        }
        else if (key < iterNode.key)
        {
            return false;
        }
    }

    return false;
}

template<typename K, typename V>
bool SkipList<K, V>::getDataReverse(const IndexBiNodePtr &pIndexBiNode, const K& key, V &value)
{
    SkipBiNodePtr pIter(NULL);
    if (!pIndexBiNode)
    {
        pIter = list.getLastNode();
    }
    else
    {
        pIter = (**pIndexBiNode).data;
    }

    for (; pIter->prev != NULL; pIter = pIter->prev)
    {
        SkipNode &iterNode = **pIter;
        if (iterNode.key == key)
        {
            value = iterNode.value;
            return true;
        }
        else if (iterNode.key < key)
        {
            return false;
        }
    }

    return false;
}

template<typename K, typename V>
bool SkipList<K, V>::getIndex(const IndexBiNodePtr &pIndexBiNode, bool forward, const K& key, V &value, 
    IndexBiNodePtr &pOutIndexBiNode, bool &outFwd)
{
    if (forward)
    {
        return getIndexForward(pIndexBiNode, key, value, pOutIndexBiNode, outFwd);
    }
    else
    {
        return getIndexReverse(pIndexBiNode, key, value, pOutIndexBiNode, outFwd);
    }
}

template<typename K, typename V>
bool SkipList<K, V>::getIndexForward(const IndexBiNodePtr &pIndexBiNode, const K& key, V &value, 
    IndexBiNodePtr &pOutIndexBiNode, bool &outFwd)
{
    IndexBiNodePtr pIter(NULL);
    if (!pIndexBiNode)
    {
        size_t indexSize = vecIndex.size();
        algo::BiLinkedList<IndexNode> &indexList = vecIndex[indexSize - 1];
        pIter = indexList.getFirstNode();
    }
    else
    {
        pIter = (**pIndexBiNode).index;
    }

    IndexBiNodePtr pIterPrev(NULL);
    for (; pIter != NULL; pIter = pIter->next)
    {
        pIterPrev = pIter;
        if ((**pIter).key == key)
        {
            pOutIndexBiNode = pIter;
            return true;
        }
        else if (key < (**pIter).key)
        {
            outFwd = false;
            pOutIndexBiNode = pIter;
            return true;
        }
    }

    if (pIterPrev)
    {
        outFwd = true;
        pOutIndexBiNode = pIterPrev;
        return true;
    }

    return false;
}

template<typename K, typename V>
bool SkipList<K, V>::getIndexReverse(const IndexBiNodePtr &pIndexBiNode, const K& key, V &value, 
    IndexBiNodePtr &pOutIndexBiNode, bool &outFwd)
{
    IndexBiNodePtr pIter(NULL);
    if (!pIndexBiNode)
    {
        size_t indexSize = vecIndex.size();
        algo::BiLinkedList<IndexNode> &indexList = vecIndex[indexSize - 1];
        pIter = indexList.getLastNode();
    }
    else
    {
        pIter = (**pIndexBiNode).index;
    }

    IndexBiNodePtr pIterNext(NULL);
    for (; pIter->prev != NULL; pIter = pIter->prev)
    {
        pIterNext = pIter;
        if ((**pIter).key == key)
        {
            pOutIndexBiNode = pIter;
            return true;
        }
        else if ((**pIter).key < key)
        {
            outFwd = true;
            pOutIndexBiNode = pIter;
            return true;
        }
    }

    if (pIterNext)
    {
        outFwd = false;
        pOutIndexBiNode = pIterNext;
        return true;
    }

    return false;
}

template<typename K, typename V>
void SkipList<K, V>::show_all()
{
    int indexSize = vecIndex.size();
    for (int i = indexSize - 1; i >= 0; --i)
    {
        algo::BiLinkedList<IndexNode> &indexList = vecIndex[i];
        std::cout<< "Index Level : " << i <<std::endl;
        IndexBiNodePtr pIter = indexList.getFirstNode();
        for (; pIter != NULL; pIter = pIter->next)
        {
            std::cout << (**pIter).key << " ";
        }
        std::cout << std::endl;
    }
    std::cout<< "Data : "<<std::endl;
    SkipBiNodePtr pIter = list.getFirstNode();
    for (; pIter != NULL; pIter = pIter->next)
    {
        std::cout << (**pIter).key << " ";
    }
    std::cout << std::endl;
}

}// namespace end


#endif
